﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DiscoveryLogic.Common.Numeric
{
    /// <summary>Resizable list holding <code>double</code> elements; implemented with arrays.
    /// First see the <a href="package-summary.html">package summary</a> and javadoc <a href="package-tree.html">tree view</a> to get the broad picture.
    /// </summary>
    [Serializable]
    public class DoubleArrayList : AbstractDoubleList, System.ICloneable
    {
        /// <summary> The array buffer into which the elements of the list are stored.
        /// The capacity of the list is the length of this array buffer.
        /// </summary>
        /// <serial>
        /// </serial>
        protected internal double[] elements_Renamed_Field;
        /// <summary> Constructs an empty list.</summary>
        public DoubleArrayList()
            : this(10)
        {
        }
        /// <summary> Constructs a list containing the specified elements. 
        /// The initial size and capacity of the list is the length of the array.
        /// 
        /// <b>WARNING:</b> For efficiency reasons and to keep memory usage low, <b>the array is not copied</b>.
        /// So if subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing.
        /// 
        /// </summary>
        /// <param name="elements">the array to be backed by the the constructed list
        /// </param>
        public DoubleArrayList(double[] elements)
        {
            this.elements(elements);
        }
        /// <summary> Constructs an empty list with the specified initial capacity.
        /// 
        /// </summary>
        /// <param name="initialCapacity">  the number of elements the receiver can hold without auto-expanding itself by allocating new internal memory.
        /// </param>
        public DoubleArrayList(int initialCapacity)
            : this(new double[initialCapacity])
        {
            SizeRaw = 0;
        }
        /// <summary> Appends the specified element to the end of this list.
        /// 
        /// </summary>
        /// <param name="element">element to be appended to this list.
        /// </param>
        public override void add(double element)
        {
            // overridden for performance only.  
            if (size_Renamed_Field == elements_Renamed_Field.Length)
                ensureCapacity(size_Renamed_Field + 1);
            elements_Renamed_Field[size_Renamed_Field++] = element;
        }
        /// <summary> Inserts the specified element before the specified position into the receiver. 
        /// Shifts the element currently at that position (if any) and
        /// any subsequent elements to the right.
        /// 
        /// </summary>
        /// <param name="index">index before which the specified element is to be inserted (must be in [0,size]).
        /// </param>
        /// <param name="element">element to be inserted.
        /// </param>
        /// <exception cref="IndexOutOfBoundsException">index is out of range (<tt>index &lt; 0 || index &gt; size()</tt>).
        /// </exception>
        public override void beforeInsert(int index, double element)
        {
            // overridden for performance only.
            if (size_Renamed_Field == index)
            {
                add(element);
                return;
            }
            if (index > size_Renamed_Field || index < 0)
                throw new System.IndexOutOfRangeException("Index: " + index + ", Size: " + size_Renamed_Field);
            ensureCapacity(size_Renamed_Field + 1);
            Array.Copy(elements_Renamed_Field, index, elements_Renamed_Field, index + 1, size_Renamed_Field - index);
            elements_Renamed_Field[index] = element;
            size_Renamed_Field++;
        }
        /// <summary> Searches the receiver for the specified value using
        /// the binary search algorithm.  The receiver must <strong>must</strong> be
        /// sorted (as by the sort method) prior to making this call.  If
        /// it is not sorted, the results are undefined: in particular, the call
        /// may enter an infinite loop.  If the receiver contains multiple elements
        /// equal to the specified object, there is no guarantee which instance
        /// will be found.
        /// 
        /// </summary>
        /// <param name="key">the value to be searched for.
        /// </param>
        /// <param name="from">the leftmost search position, inclusive.
        /// </param>
        /// <param name="to">the rightmost search position, inclusive.
        /// </param>
        /// <returns> index of the search key, if it is contained in the receiver;
        /// otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The <i>insertion
        /// point</i> is defined as the the point at which the value would
        /// be inserted into the receiver: the index of the first
        /// element greater than the key, or <tt>receiver.size()</tt>, if all
        /// elements in the receiver are less than the specified key.  Note
        /// that this guarantees that the return value will be &gt;= 0 if
        /// and only if the key is found.
        /// </returns>
        /// <seealso cref="cern.colt.Sorting">
        /// </seealso>
        /// <seealso cref="java.util.Arrays">
        /// </seealso>
        public override int binarySearchFromTo(double key, int from, int to)
        {
            return Sorting.binarySearchFromTo(this.elements_Renamed_Field, key, from, to);
        }
        /// <summary> Returns a deep copy of the receiver. 
        /// 
        /// </summary>
        /// <returns>  a deep copy of the receiver.
        /// </returns>
        public override System.Object Clone()
        {
            // overridden for performance only.
            DoubleArrayList clone = new DoubleArrayList((double[])elements_Renamed_Field.Clone());
            clone.SizeRaw = size_Renamed_Field;
            return clone;
        }
        /// <summary> Returns a deep copy of the receiver; uses <code>clone()</code> and casts the result.
        /// 
        /// </summary>
        /// <returns>  a deep copy of the receiver.
        /// </returns>
        public virtual DoubleArrayList copy()
        {
            return (DoubleArrayList)Clone();
        }
        /// <summary> Returns the elements currently stored, including invalid elements between size and capacity, if any.
        /// 
        /// <b>WARNING:</b> For efficiency reasons and to keep memory usage low, <b>the array is not copied</b>.
        /// So if subsequently you modify the returned array directly via the [] operator, be sure you know what you're doing.
        /// 
        /// </summary>
        /// <returns> the elements currently stored.
        /// </returns>
        public override double[] elements()
        {
            return elements_Renamed_Field;
        }
        /// <summary> Sets the receiver's elements to be the specified array (not a copy of it).
        /// 
        /// The size and capacity of the list is the length of the array.
        /// <b>WARNING:</b> For efficiency reasons and to keep memory usage low, <b>the array is not copied</b>.
        /// So if subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing.
        /// 
        /// </summary>
        /// <param name="elements">the new elements to be stored.
        /// </param>
        /// <returns> the receiver itself.
        /// </returns>
        public override AbstractDoubleList elements(double[] elements)
        {
            this.elements_Renamed_Field = elements;
            this.size_Renamed_Field = elements.Length;
            return this;
        }
        /// <summary> Ensures that the receiver can hold at least the specified number of elements without needing to allocate new internal memory.
        /// If necessary, allocates new internal memory and increases the capacity of the receiver.
        /// 
        /// </summary>
        /// <param name="minCapacity">  the desired minimum capacity.
        /// </param>
        public override void ensureCapacity(int minCapacity)
        {
            elements_Renamed_Field = Arrays.ensureCapacity(elements_Renamed_Field, minCapacity);
        }
        /// <summary> Compares the specified Object with the receiver.  
        /// Returns true if and only if the specified Object is also an ArrayList of the same type, both Lists have the
        /// same size, and all corresponding pairs of elements in the two Lists are identical.
        /// In other words, two Lists are defined to be equal if they contain the
        /// same elements in the same order.
        /// 
        /// </summary>
        /// <param name="otherObj">the Object to be compared for equality with the receiver.
        /// </param>
        /// <returns> true if the specified Object is equal to the receiver.
        /// </returns>
        public override bool Equals(System.Object otherObj)
        {
            //delta
            // overridden for performance only.
            if (!(otherObj is DoubleArrayList))
                return base.Equals(otherObj);
            if (this == otherObj)
                return true;
            if (otherObj == null)
                return false;
            DoubleArrayList other = (DoubleArrayList)otherObj;
            if (size() != other.size())
                return false;

            double[] theElements = elements();
            double[] otherElements = other.elements();
            for (int i = size(); --i >= 0; )
            {
                if (theElements[i] != otherElements[i])
                    return false;
            }
            return true;
        }
        /// <summary> Applies a procedure to each element of the receiver, if any.
        /// Starts at index 0, moving rightwards.
        /// </summary>
        /// <param name="procedure">   the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise continues. 
        /// </param>
        /// <returns> <tt>false</tt> if the procedure stopped before all elements where iterated over, <tt>true</tt> otherwise. 
        /// </returns>
        public override bool forEach(DoubleProcedure procedure)
        {
            // overridden for performance only.
            double[] theElements = elements_Renamed_Field;
            int theSize = size_Renamed_Field;

            for (int i = 0; i < theSize; )
                if (!procedure.apply(theElements[i++]))
                    return false;
            return true;
        }
        /// <summary> Returns the element at the specified position in the receiver.
        /// 
        /// </summary>
        /// <param name="index">index of element to return.
        /// </param>
        /// <exception cref="IndexOutOfBoundsException">index is out of range (index
        /// &lt; 0 || index &gt;= size()).
        /// </exception>
        public override double get_Renamed(int index)
        {
            // overridden for performance only.
            if (index >= size_Renamed_Field || index < 0)
                throw new System.IndexOutOfRangeException("Index: " + index + ", Size: " + size_Renamed_Field);
            return elements_Renamed_Field[index];
        }
        /// <summary> Returns the element at the specified position in the receiver; <b>WARNING:</b> Does not check preconditions. 
        /// Provided with invalid parameters this method may return invalid elements without throwing any exception!
        /// <b>You should only use this method when you are absolutely sure that the index is within bounds.</b>
        /// Precondition (unchecked): <tt>index &gt;= 0 && index &lt; size()</tt>.
        /// 
        /// </summary>
        /// <param name="index">index of element to return.
        /// </param>
        public override double getQuick(int index)
        {
            return elements_Renamed_Field[index];
        }
        /// <summary> Returns the index of the first occurrence of the specified
        /// element. Returns <code>-1</code> if the receiver does not contain this element.
        /// Searches between <code>from</code>, inclusive and <code>to</code>, inclusive.
        /// Tests for identity.
        /// 
        /// </summary>
        /// <param name="element">element to search for.
        /// </param>
        /// <param name="from">the leftmost search position, inclusive.
        /// </param>
        /// <param name="to">the rightmost search position, inclusive.
        /// </param>
        /// <returns>  the index of the first occurrence of the element in the receiver; returns <code>-1</code> if the element is not found.
        /// </returns>
        /// <exception cref="IndexOutOfBoundsException">index is out of range (<tt>size()&gt;0 && (from&lt;0 || from&gt;to || to&gt;=size())</tt>).
        /// </exception>
        public override int indexOfFromTo(double element, int from, int to)
        {
            // overridden for performance only.
            if (size_Renamed_Field == 0)
                return -1;
            checkRangeFromTo(from, to, size_Renamed_Field);

            double[] theElements = elements_Renamed_Field;
            for (int i = from; i <= to; i++)
            {
                if (element == theElements[i])
                {
                    return i;
                } //found
            }
            return -1; //not found
        }
        /// <summary> Returns the index of the last occurrence of the specified
        /// element. Returns <code>-1</code> if the receiver does not contain this element.
        /// Searches beginning at <code>to</code>, inclusive until <code>from</code>, inclusive.
        /// Tests for identity.
        /// 
        /// </summary>
        /// <param name="element">element to search for.
        /// </param>
        /// <param name="from">the leftmost search position, inclusive.
        /// </param>
        /// <param name="to">the rightmost search position, inclusive.
        /// </param>
        /// <returns>  the index of the last occurrence of the element in the receiver; returns <code>-1</code> if the element is not found.
        /// </returns>
        /// <exception cref="IndexOutOfBoundsException">index is out of range (<tt>size()&gt;0 && (from&lt;0 || from&gt;to || to&gt;=size())</tt>).
        /// </exception>
        public override int lastIndexOfFromTo(double element, int from, int to)
        {
            // overridden for performance only.
            if (size_Renamed_Field == 0)
                return -1;
            checkRangeFromTo(from, to, size_Renamed_Field);

            double[] theElements = elements_Renamed_Field;
            for (int i = to; i >= from; i--)
            {
                if (element == theElements[i])
                {
                    return i;
                } //found
            }
            return -1; //not found
        }
        /// <summary> Returns a new list of the part of the receiver between <code>from</code>, inclusive, and <code>to</code>, inclusive.</summary>
        /// <param name="from">the index of the first element (inclusive).
        /// </param>
        /// <param name="to">the index of the last element (inclusive).
        /// </param>
        /// <returns> a new list
        /// </returns>
        /// <exception cref="IndexOutOfBoundsException">index is out of range (<tt>size()&gt;0 && (from&lt;0 || from&gt;to || to&gt;=size())</tt>).
        /// </exception>
        public override AbstractDoubleList partFromTo(int from, int to)
        {
            if (size_Renamed_Field == 0)
                return new DoubleArrayList(0);

            checkRangeFromTo(from, to, size_Renamed_Field);

            double[] part = new double[to - from + 1];
            Array.Copy(elements_Renamed_Field, from, part, 0, to - from + 1);
            return new DoubleArrayList(part);
        }
        /// <summary> Removes from the receiver all elements that are contained in the specified list.
        /// Tests for identity.
        /// 
        /// </summary>
        /// <param name="other">the other list.
        /// </param>
        /// <returns> <code>true</code> if the receiver changed as a result of the call.
        /// </returns>
        public override bool removeAll(AbstractDoubleList other)
        {
            // overridden for performance only.
            if (!(other is DoubleArrayList))
                return base.removeAll(other);

            /* There are two possibilities to do the thing
            a) use other.indexOf(...)
            b) sort other, then use other.binarySearch(...)
			
            Let's try to figure out which one is faster. Let M=size, N=other.size, then
            a) takes O(M*N) steps
            b) takes O(N*logN + M*logN) steps (sorting is O(N*logN) and binarySearch is O(logN))
			
            Hence, if N*logN + M*logN < M*N, we use b) otherwise we use a).
            */
            if (other.size() == 0)
            {
                return false;
            } //nothing to do
            int limit = other.size() - 1;
            int j = 0;
            double[] theElements = elements_Renamed_Field;
            int mySize = size();

            double N = (double)other.size();
            double M = (double)mySize;
            if ((N + M) * Arithmetic.log2(N) < M * N)
            {
                // it is faster to sort other before searching in it
                DoubleArrayList sortedList = (DoubleArrayList)other.Clone();
                sortedList.quickSort();

                for (int i = 0; i < mySize; i++)
                {
                    if (sortedList.binarySearchFromTo(theElements[i], 0, limit) < 0)
                        theElements[j++] = theElements[i];
                }
            }
            else
            {
                // it is faster to search in other without sorting
                for (int i = 0; i < mySize; i++)
                {
                    if (other.indexOfFromTo(theElements[i], 0, limit) < 0)
                        theElements[j++] = theElements[i];
                }
            }

            bool modified = (j != mySize);
            Size = j;
            return modified;
        }
        /// <summary> Replaces a number of elements in the receiver with the same number of elements of another list.
        /// Replaces elements in the receiver, between <code>from</code> (inclusive) and <code>to</code> (inclusive),
        /// with elements of <code>other</code>, starting from <code>otherFrom</code> (inclusive).
        /// 
        /// </summary>
        /// <param name="from">the position of the first element to be replaced in the receiver
        /// </param>
        /// <param name="to">the position of the last element to be replaced in the receiver
        /// </param>
        /// <param name="other">list holding elements to be copied into the receiver.
        /// </param>
        /// <param name="otherFrom">position of first element within other list to be copied.
        /// </param>
        public override void replaceFromToWithFrom(int from, int to, AbstractDoubleList other, int otherFrom)
        {
            // overridden for performance only.
            if (!(other is DoubleArrayList))
            {
                // slower
                base.replaceFromToWithFrom(from, to, other, otherFrom);
                return;
            }
            int length = to - from + 1;
            if (length > 0)
            {
                checkRangeFromTo(from, to, size());
                checkRangeFromTo(otherFrom, otherFrom + length - 1, other.size());
                Array.Copy(((DoubleArrayList)other).elements_Renamed_Field, otherFrom, elements_Renamed_Field, from, length);
            }
        }
        /// <summary> Retains (keeps) only the elements in the receiver that are contained in the specified other list.
        /// In other words, removes from the receiver all of its elements that are not contained in the
        /// specified other list. 
        /// </summary>
        /// <param name="other">the other list to test against.
        /// </param>
        /// <returns> <code>true</code> if the receiver changed as a result of the call.
        /// </returns>
        public override bool retainAll(AbstractDoubleList other)
        {
            // overridden for performance only.
            if (!(other is DoubleArrayList))
                return base.retainAll(other);

            /* There are two possibilities to do the thing
            a) use other.indexOf(...)
            b) sort other, then use other.binarySearch(...)
			
            Let's try to figure out which one is faster. Let M=size, N=other.size, then
            a) takes O(M*N) steps
            b) takes O(N*logN + M*logN) steps (sorting is O(N*logN) and binarySearch is O(logN))
			
            Hence, if N*logN + M*logN < M*N, we use b) otherwise we use a).
            */
            int limit = other.size() - 1;
            int j = 0;
            double[] theElements = elements_Renamed_Field;
            int mySize = size();

            double N = (double)other.size();
            double M = (double)mySize;
            if ((N + M) * Arithmetic.log2(N) < M * N)
            {
                // it is faster to sort other before searching in it
                DoubleArrayList sortedList = (DoubleArrayList)other.Clone();
                sortedList.quickSort();

                for (int i = 0; i < mySize; i++)
                {
                    if (sortedList.binarySearchFromTo(theElements[i], 0, limit) >= 0)
                        theElements[j++] = theElements[i];
                }
            }
            else
            {
                // it is faster to search in other without sorting
                for (int i = 0; i < mySize; i++)
                {
                    if (other.indexOfFromTo(theElements[i], 0, limit) >= 0)
                        theElements[j++] = theElements[i];
                }
            }

            bool modified = (j != mySize);
            Size = j;
            return modified;
        }
        /// <summary> Reverses the elements of the receiver.
        /// Last becomes first, second last becomes second first, and so on.
        /// </summary>
        public override void reverse()
        {
            // overridden for performance only.
            double tmp;
            int limit = size_Renamed_Field / 2;
            int j = size_Renamed_Field - 1;

            double[] theElements = elements_Renamed_Field;
            for (int i = 0; i < limit; )
            {
                //swap
                tmp = theElements[i];
                theElements[i++] = theElements[j];
                theElements[j--] = tmp;
            }
        }
        /// <summary> Replaces the element at the specified position in the receiver with the specified element.
        /// 
        /// </summary>
        /// <param name="index">index of element to replace.
        /// </param>
        /// <param name="element">element to be stored at the specified position.
        /// </param>
        /// <exception cref="IndexOutOfBoundsException">index is out of range (index
        /// &lt; 0 || index &gt;= size()).
        /// </exception>
        public override void set_Renamed(int index, double element)
        {
            // overridden for performance only.
            if (index >= size_Renamed_Field || index < 0)
                throw new System.IndexOutOfRangeException("Index: " + index + ", Size: " + size_Renamed_Field);
            elements_Renamed_Field[index] = element;
        }
        /// <summary> Replaces the element at the specified position in the receiver with the specified element; <b>WARNING:</b> Does not check preconditions.
        /// Provided with invalid parameters this method may access invalid indexes without throwing any exception!
        /// <b>You should only use this method when you are absolutely sure that the index is within bounds.</b>
        /// Precondition (unchecked): <tt>index &gt;= 0 && index &lt; size()</tt>.
        /// 
        /// </summary>
        /// <param name="index">index of element to replace.
        /// </param>
        /// <param name="element">element to be stored at the specified position.
        /// </param>
        public override void setQuick(int index, double element)
        {
            elements_Renamed_Field[index] = element;
        }
        /// <summary> Randomly permutes the part of the receiver between <code>from</code> (inclusive) and <code>to</code> (inclusive). </summary>
        /// <param name="from">the index of the first element (inclusive) to be permuted.
        /// </param>
        /// <param name="to">the index of the last element (inclusive) to be permuted.
        /// </param>
        /// <exception cref="IndexOutOfBoundsException">index is out of range (<tt>size()&gt;0 && (from&lt;0 || from&gt;to || to&gt;=size())</tt>).
        /// </exception>
        public override void shuffleFromTo(int from, int to)
        {
            // overridden for performance only.
            if (size_Renamed_Field == 0)
            {
                return;
            }
            checkRangeFromTo(from, to, size_Renamed_Field);

            System.DateTime tempAux = System.DateTime.Now;
            //UPGRADE_NOTE: ref keyword was added to struct-type parameters. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1303'"
            Uniform gen = new Uniform(new DRand(ref tempAux));
            double tmpElement;
            double[] theElements = elements_Renamed_Field;
            int random;
            for (int i = from; i < to; i++)
            {
                random = gen.nextIntFromTo(i, to);

                //swap(i, random)
                tmpElement = theElements[random];
                theElements[random] = theElements[i];
                theElements[i] = tmpElement;
            }
        }
        /// <summary> Trims the capacity of the receiver to be the receiver's current 
        /// size. Releases any superfluos internal memory. An application can use this operation to minimize the 
        /// storage of the receiver.
        /// </summary>
        public override void trimToSize()
        {
            elements_Renamed_Field = Arrays.trimToCapacity(elements_Renamed_Field, size());
        }
        //UPGRADE_NOTE: The following method implementation was automatically added to preserve functionality. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1306'"
        public override int GetHashCode()
        {
            return base.GetHashCode();
        }
    }
}
